Current computer microprocessors are designed to execute binary machine code instructions. Because it is burdensome to program directly at the machine code level, computer software is normally written in a high-level programming language which is then converted into executable machine code instructions. As shown in FIG. 9, a high-level source code program 900 may be converted by a compiler 902 into binary machine code 904 which may be executed by a particular type of microprocessor hardware 908. The binary machine code 904 is composed using an instruction set specific to a particular type of microprocessor. This instruction set is part of the microprocessor's instruction set architecture (ISA) 906 which provides the binary code 904 with a functional interface to the microprocessor hardware 908.
In the course of the evolution of microprocessors, various different families of microprocessors have been designed with distinct ISAs. In addition, when microprocessors within a given family evolve, their ISAs often evolve as well. Consequently, binary code 904 that is executable on an existing type of microprocessor 908 and its associated ISA 906 does not necessarily execute on a newer or different type of microprocessor 918 with a different ISA 916. This situation gives rise to the problem of software portability, i.e., allowing legacy software to run on a new or different ISA. One approach to address this software portability problem is to re-compile the high-level source code program 900 using a new compiler 912 designed to generate machine code 914 specific to the different ISA 916. Sometimes, however, the high-level source code is not available or a compiler program 912 for the new ISA 916 is not available. Another technique is to use an emulator program running on the new processor 918 which emulates the old processor 908 and executes the existing binary code 904. As with re-compiling, sometimes an emulator for the new ISA 916 is not available. In addition, emulators often add a significant runtime overhead.
Another approach to addressing the software portability problem is binary translation. Binary translation 910 is a process that directly converts compiled binary machine code 904 from a source ISA 906 to binary machine code 914 on a target ISA 916, without knowledge of any pre-compiled high-level source code 900. Binary translation may be performed dynamically or statically, i.e., on-the-fly as the code is executed or once-and-for-all before execution.
The first binary translators were custom-designed by computer manufacturers to facilitate transition to computers based on new microprocessor hardware. For example, Digital Equipment Corporation used binary translation to migrate users of VAX, MIPS, SPARC and x86 to Alpha. Apple Computer used binary translation to run Motorola 68000 programs on their PowerPC machines. Other applications of binary translation are to provide machine virtualization and to provide forward and backward compatibility between ISA generations.
A common feature in all these binary translation tools is that they are all custom-designed to solve a specific problem and are tightly coupled to the source and target ISAs and operating systems. This type of binary translator requires several man years of development. One of the main challenges in writing a binary translator is dealing with the vagaries of instruction sets of different architectures. The process of manually modeling the instruction semantics and then writing an optimizer to exploit them is daunting, error-prone and unsuitable for scaling to many different architectures. Thus, when a new ISA is created, considerable development effort is required to create a new binary translator for that ISA.
Motivated by the high development cost of custom-designed binary translators, some researchers have proposed a general purpose binary translator that is more easily adaptable to changes in both source and target ISA, i.e., resourceable and retargetable. These general purpose binary translators use an intermediate representation as part of a multi-step translation, i.e., these techniques do not perform direct translation from one ISA to another ISA. For example, FIG. 8 illustrates one such binary translator design. Binary machine code 800 specific to a source ISA is first decoded to an intermediate, machine-independent representation of the program 802, called a register transfer list (RTL). A high-level analysis of this abstract RTL 802 produces an abstract RTL 804, which is then used to generate the translated machine code 806 specific to the target ISA. This approach to general purpose binary translation, however, still requires considerable effort to adapt the translator to a new source or target ISA, i.e., to develop new rules for decoding from the new source ISA to the RTL or for encoding (efficiently) to the new target ISA from the RTL. Moreover, a general purpose binary translator of this type requires a universal RTL language that can capture the peculiarities of all existing ISAs. If a sufficiently different ISA is developed in the future, however, the RTL may need to be redesigned, defeating the purpose of the approach.
Other approaches to binary translation avoid dealing with the complexity of different instruction sets by encoding each instruction as a series of operations in C. This allows support for many source-target pairs. This ease of adaptation, however, is gained only with a significant reduction of performance (typically a factor of five slowdown).
It remains an outstanding problem in the art to provide a binary translator that can be easily adapted to a new source-target architecture pair and also maintain a high level of performance.
Peephole Optimization and Binary Translation
To improve the efficiency of the target ISA machine code, some existing binary translators use code optimization techniques in a post-processing step after translation to the target ISA. For example, peephole optimization is a known technique for locally replacing small sets of computer program instructions (“peepholes”) with more efficient instructions (that are not necessarily “optimal”) on the same ISA. Traditionally, peephole optimization is implemented using a collection of human-designed pattern matching algorithms or rules to recognize and replace different common types of code patterns. In particular, the use of manually selected peephole optimization rules to optimize the machine code on the target ISA after translation is known. For example, U.S. Pat. No. 6,820,255 presents a technique for binary translation that, after translation is completed, uses peephole optimization rules on the target ISA to optimize the translated code. Because these peephole optimization rules are manually selected, it can take significant time and effort to produce a comprehensive and efficient set of code optimization rules. It is also significant to emphasize that these peephole optimization techniques are used to optimize code on a single, fixed target ISA after translation is completed. They are not part of the binary translation process proper and do not involve code on more than one ISA. These optimization techniques, therefore, do not address the basic challenge of binary translation, which is to ensure both optimal translated code and easy adaptation to new source-target ISA pairs.